package com.example.algorithm.sorts;

/**
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
 * 请你找出并返回这两个正序数组的中位数 。
 * <p>
 * 示例 1：
 * <p>
 * 输入：nums1 = [1,3], nums2 = [2]
 * 输出：2.00000
 * 解释：合并数组 = [1,2,3] ，中位数 2
 * <p>
 * 示例 2：
 * <p>
 * 输入：nums1 = [1,2], nums2 = [3,4]
 * 输出：2.50000
 * 解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
 */
public class Leetcode4_FindMedianSortedArrays {
    public static void main(String[] args) {
        int[] nums1 = {3, 4};
        int[] nums2 = {1, 7};
        System.out.println(findMedianSortedArrays(nums1, nums2));

    }

    /**
     * 解法一:根据归并排序的归的过程来完成两个有序数组的合并变形，得到中位数
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 定义两个变量用于记录当前第i-1大的数和第i大的数
        int m1 = 0, m2 = 0;
        // 定义两个指针分别用于遍历两个数组
        int p1 = 0, p2 = 0;
        for (int i = 0; i <= (nums1.length + nums2.length) / 2; i++) {
            m1 = m2;

            if (p1 < nums1.length && (p2 >= nums2.length || nums1[p1] < nums2[p2])) {
                m2 = nums1[p1++];
            } else {
                m2 = nums2[p2++];
            }
        }

        // 先判断两个数组元素个数之和奇偶性
        if ((nums1.length + nums2.length) % 2 == 0) {
            return (m1 + m2) / 2.0;
        } else {
            return m2;
        }
    }

    /**
     * 解法二:二分查找结合中位数特点
     * <p>
     * 思路:
     * 中位数特点:
     * 中位数可以将数组分成2份
     * <p>
     * 寻找中位数的问题就可以变为寻找满足下列条件的分界线：
     * 1. 分界线左边的元素都小于等于分界线右边的元素
     * 2. 0 <=分界线左边的元素个数-分界线右边的元素个数<=1
     * <p>
     * 由第二条性质可以得出分界线在一个数组中确定了位置，那么另一个数组的位置也已经确定了
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public static double findMedianSortedArrays2(int[] nums1, int[] nums2) {
        int m = nums1.length, n = nums2.length;

        // 较短的数组在前，确保m <= n
        if (m > n) {
            return findMedianSortedArrays2(nums2, nums1);
        }

        //定义p、q为nums1分界线范围，共m+1个可能的划分位置
        int p = 0, q = m;
        //nums1、num2的分界位置
        int i = 0, j = 0;
        while (p <= q) {
            //⼆二分确定nums1当前分界位置
            i = (p + q) / 2;
            //根据i确定nums2的分界位置，使得左侧元素数-右侧元素数为0或1
            j = (m + n + 1) / 2 - i;
            //nums1右侧最⼩小值⼩小于nums2左侧最⼤大值，nums1划分位置在[i+1, q]之间
            if (j != 0 && i != m && nums1[i] < nums2[j - 1])
                p = i + 1;
            else if (i != 0 && j != n && nums1[i - 1] > nums2[j]) {
                //nums1左侧最⼤大值⼤大于nums2右侧最⼩小值，nums1划分位置在[p, i-1]之间
                q = i - 1;
            } else {//当前划分位置左侧的最⼤大值⼩小于右侧的最⼩小值，满⾜足要求
                break;
            }
        }
        //m+n为奇数，返回左侧的最⼤大值
        //左侧最⼤大值：三种情况 nums1为空、nums2为空、都不不为空
        int maxLeft = i == 0 ? nums2[j - 1] : (j == 0 ? nums1[i - 1] : Math.max(nums1[i - 1], nums2[j - 1]));
        if ((m + n) % 2 == 1)
            return maxLeft;
        //m+n为偶数，返回左侧最⼤大值与右侧最⼩小值的平均
        //右侧最⼩小值：三种情况 nums1为空、nums2为空、都不不为空
        int minRight = i == m ? nums2[j] : (j == n ? nums1[i] : Math.min(nums1[i], nums2[j]));
        return (maxLeft + minRight) / 2.0;
    }
}
